import java.util.LinkedList;
import java.util.List;

public class question_60 {
}
//60排列序列
class Solution_60 {
    //这倒题是一道关于全排列的题目，然后找到排序之后再第k个的那个数
    //这倒题我原本的想法是直接去递归，因为数组原本有序，dfs访问的顺序实际也是从小到大的，
    //然后我想到了剪枝的思想，他又没有说要我们把遍历的结束输出，只是输出第k位的值，这样的话其实我直接
    //按照数学规律就可以了，详细见下面的代码
    public List<Integer> l=new LinkedList<>();
    public String getPermutation(int n, int k) {
        int arr[]=new int [n];
        boolean err[]=new boolean[n];
        int orr[]=new int[n];
        int ceng=0;
        for (int i = 1; i <=n; i++) {
            arr[i-1]=i;
        }
        dfs(arr,err,ceng,orr,n);
        return Integer.toString(l.get(k).intValue());

    }
    public void dfs(int arr[],boolean err[],int ceng,int orr[],int n){
        if(ceng==n){
            int temp=0;
            for (int i = 0; i < n; i++) {
                temp=temp*10+orr[i];
            }
            l.add(temp);
            return;
        }
        for (int i = 0; i < n; i++) {
            if(err[i]==false){//说明还没选择
                err[i]=true;
                orr[ceng]=arr[i];
                dfs(arr,err,ceng+1,orr,n);
                //遍历结束之后把状态重新改回来
                err[i]=false;
            }
        }
    }

    public static void main(String[] args) {
        Solution_60 s = new Solution_60();
        s.getPermutation(3,3);
    }
}
